package myself.a007Bucket;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/24
 * Time 21:54
 * Mail 739153436@qq.com
 */
public class RadixSort {
    // only for no-negative value
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = max > i ? max : i;
        }
        int res = 0;
        while (max != 0) {
            max /= 10;
            res++;
        }
        return res;
    }

    // 对数组进行升序排序
    // arr[L..R]排序  ,  最大值的十进制位数digit
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int capacity = 10;

        for (int dig = 1; dig <= digit; dig++) {
            // 计数桶
            int[] count = new int[capacity];
            for (int j = L; j <= R; j++) {
                int index = getDigit(arr[j], dig);
                count[index]++;
            }

            // 累加桶
            for (int i = 1; i < count.length; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 排序，复制到目标数组
            int[] temp = new int[R - L + 1];
            for (int i = R; i >= L; i--) {
                int index = getDigit(arr[i], dig);
                temp[--count[index]] = arr[i];
            }

            for (int i = 0; i < temp.length; i++) {
                arr[L + i] = temp[i];
            }
        }
    }

    /**
     * 取出某一位上的取余的数，比如个位、十位
     *
     * @param x 目标数
     * @param d 所在的位数，1表示个位，2表示十位
     * @return 余数
     */
    public static int getDigit(int x, int d) {
        return (x / (int) (Math.pow(10, d - 1))) % 10;
    }
}
